/**
//给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。 
//
// 插入排序 算法的步骤: 
//
// 
// 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 
// 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 
// 重复直到所有输入数据插入完为止。 
// 
//
// 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表
//中。 
//
// 对链表进行插入排序。 
//
// 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入: head = [4,2,1,3]
//输出: [1,2,3,4] 
//
// 示例 2： 
//
// 
//
// 
//输入: head = [-1,5,3,4,0]
//输出: [-1,0,3,4,5] 
//
// 
//
// 提示： 
//
// 
//
// 
// 列表中的节点数在 [1, 5000]范围内 
// -5000 <= Node.val <= 5000 
// 
// Related Topics 链表 排序 👍 513 👎 0

*/

package com.xixi.basicAlgroithms.sort;


public class ID00147InsertionSortList {

public static class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

public static void main(String[] args) {

    Solution solution = new ID00147InsertionSortList().new Solution();
    ListNode tail = new ListNode(3, null);
    ListNode next2 = new ListNode(1, tail);
    ListNode next1 = new ListNode(2, next2);
    ListNode head = new ListNode(4, next1);

    solution.insertionSortList(head);


}


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null) return head; //如果只有一个节点
        //初始化指针
        ListNode newHead = new ListNode();//先建立一个哨兵节点
        newHead.next = head; //哨兵节点的next指针指向当前数组的头节点

        ListNode judgeNode = head.next; //待判定节点，假设第一个节点已经排序
        head.next = null; //避免循环，先把已排序区置空

        while(judgeNode !=null ){ //直到判定节点等于null了，就说明全都判定完了
            ListNode currentNode = newHead.next; //当前节点，每次判断都从头节点开始遍历
            ListNode preNode = newHead; //保存当前节点的前一个节点

            ListNode nextJudgeNode = judgeNode.next; //保存下一个待判定节点的指针

            while(currentNode != null){ //直到判定到排序区尾部
                if(currentNode.val > judgeNode.val){ //当前节点比待判定节点大，就插到当前节点前面；
                    judgeNode.next = currentNode; //首先把待判定节点的next指针指向当前节点

                    preNode.next = judgeNode; //再把当前节点的前一个节点指向当前节点
                    break;
                }
                //指针移动到下一个已排序的节点
                preNode = currentNode;
                currentNode = currentNode.next;
            }

            //如果移动到最后一个节点都没插入，那么做特殊处理
            if(preNode.next == null){
                preNode.next = judgeNode;
                judgeNode.next = null; //把当前节点查到已排序区的最后
            }


            //指针移动到下一个待判定节点
            judgeNode = nextJudgeNode;
        }



        return  newHead.next;

    }



}
//leetcode submit region end(Prohibit modification and deletion)




}